A common objective of digital design is the recognition of a given bit pattern or sequence in some bit stream or data sequence. Digital devices which perform such pattern recognition are known as "state machines". Such machines are designed to accept binary data sequences as input, and to produce a predetermined output if a given data sequence is included in the input. For instance, a state machine may be designed to "go-high" if it encounters the trigger sequence 10101010 within an input data sequence. Therefore, the input 0010101010111 would trigger the machine because the trigger sequence was included in the input data sequence. On the other hand, the input 0010101011111 would not trigger the machine because the requisite trigger was not present in the input data sequence. Such a state machine is therefore designed to recognize the trigger sequence. Techniques for the efficient design of such state machines and for constructing them with logic components and various types of flip-flop circuits are well known in electrical engineering. Switching and Finite Automata Theory, Part III, by Zvi Kohavi, (McGraw-Hill, 1978).
There is great need for the pattern recognition capability provided by state machines in modern digital equipment. One such important application involves so-called Local Area Networks (LAN). A LAN is a communication network that provides interconnection of a variety of data communicating devices within a small area. Local Networks, p. 2, by William Stallings (Macmillan Publishing Company, 1984).
A typical LAN is a computer network limited to a geographically small area such as a plant site or an office building. various devices, such as computers, terminals, etc. are "plugged into" the network at various locations on the network. Each device is assigned an address so that digital communications between devices on the network may be properly delivered and received. Obviously, each device must be able to recognize its own address, among other things, thus necessitating pattern recognition as discussed above.
A well known and commercially accepted LAN standard is encompassed by the Institute of Electrical and Electronic Engineers (IEEE) standard 802.3. This standard is well known in industry under the name "Ethernet." The IEEE 802.3 standard features a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) media access method whereby two or more stations (devices) share a common bus transmission medium, typically a coaxial cable. To transmit over the LAN, a station or device waits for a quiet period on the bus, that is, no other station is transmitting, and then sends its intended message in bit serial form, at rates up to 10 Mbits/sec.
In the Ethernet or IEEE 802.3 system, messages between devices on the network travel in packets or frames on the bus. An Ethernet packet is displayed in FIG. 1. In examining the packet from head to tail, we see that it consists of a 64-bit preamble, a 48-bit destination address, a 48-bit source address, a 16-bit type field, a data field that may be from 46 bytes up to 1500 bytes long, wherein the last 4 bytes constitute 32-bit cyclic redundancy check or frame check sequence. This Ethernet message format establishes the standard required for widespread implementation of LAN technology.
An important segment of LAN technology involves data communications test equipment, commonly known as protocol analyzers. These devices are designed to monitor, as well as generate, traffic on the LAN or Ethernet transmission bus and then analyze it for the purposes of field service; electronic data processing center support; network component research, development, manufacture, installation and service; and general network troubleshooting.
Often, examination of the fields of Ethernet packets will be necessary. For instance, error analysis may require detection of all Ethernet packets in traffic which have certain parameters, for example, every fourth byte of the data field is a certain ASCII (American Standards Committee on Information Interchange) character. Thus, one may be interested in packets with data fields fitting a certain pattern.
As noted earlier, pattern recognition is the task of state machines. However, conventional state machines are often too awkward for the sort of rapid data recognition requirements of the latest Ethernet system protocol analyzers and similar systems. A major shortcoming is that while a given pattern may be spotted with a conventional state machine, changing the patterns to be recognized would require tedious redesign and reconstruction of the state machine. Such a limitation obviously makes efficient error analysis of Ethernet systems, for instance, nearly impossible. Also, trapping deep into the data field with a conventional state machine requires an excessive amount of hardware.